package com.LeeCode;

import java.util.ArrayList;

/**
 * 反转链表
 **/

public class Code206 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        ListNode head = Utils.arrayToListNode(nums);
        Utils.printListNode(head);

        System.out.println();
        ListNode res = new Code206().reverseList1(head);
        Utils.printListNode(res);
    }

    public ListNode reverseList(ListNode head) {
        if (head == null)
            return null;
        ArrayList<ListNode> list = new ArrayList<>();

        while (head != null) {
            list.add(head);
            head = head.next;
        }

        for (int i = list.size() - 1; i > 0; i--) {
            list.get(i).next = list.get(i - 1);
        }
        list.get(0).next = null;
        return list.get(list.size() - 1);
    }

    public ListNode reverseList1(ListNode head) {
        if (head == null)
            return null;

        ListNode pre = null, cur = head, tmp;
        while (cur != null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    public ListNode reverseList2(ListNode head) {
        // 终止条件：空链表或只有一个节点
        if (head == null || head.next == null) {
            return head;
        }

        // 递归翻转后面的链表，并得到新的头节点
        ListNode newHead = reverseList(head.next);

        // 当前节点接到翻转后链表的末尾
        head.next.next = head;

        // 断开原来的连接，防止循环
        head.next = null;

        // 返回新的头节点
        return newHead;
    }
}
